/*================================================================
*   Copyright (C) 2020 belonging to YangZhengQing. All rights reserved.
*   
*   文件名称：mytest.c
*   创 建 者：YangZhengQing
*   创建日期：2020年03月02日
*   描    述：
*
*================================================================*/


//#include "mytest.h"

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>


/*
   功能：寻找矩阵路径
   参数：
   board：矩阵
   boardSize：矩阵行大小
   boardColSize：矩阵列大小
   word：待寻数组
   返回：
   找到返回true，反之返回false
 */

bool look_path(char *matrix , int rows, int cols, int row, int col, int path_length, char *str, int *visited);

bool exist(char** board, int boardSize, int* boardColSize, char* word){

	int             row;//当前行
	int             col;//当前列
	int             rows = boardSize;//总行
	int             cols = *boardColSize;//矩阵列大小
	int             *visited = (int *)malloc((rows*cols)*sizeof(int));//申请标记寻过格子的空间
	int             rv = false;
	int             path_length = 0;//走过的路径长度

	printf("rows=%d,cols=%d\n",rows,cols);

	memset(visited, 0, rows*cols*sizeof(int));//初始化维00;

	//开始从第一行第一列开始逐个寻找路径
	for(row = 0; row < rows; row++)
	{
		for(col = 0;col < cols; col++)
		{
			rv = look_path(*board,rows,cols,row,col,path_length,word,visited);//
			if(rv == true)
			{
				return rv;
			}
		}
	}

	free(visited);

	return false;
}



/*
   功能：在矩阵中寻找字符
   参数：
   matrix：矩阵
   rows：行
   cols：列
   str：待寻找字符串
   row：当前格子所在的行
   col：当前格子所在的列
   pathLength：当前路径的长度
   visited：标记已经走过的格子

   返回值：
   路径找到返回true，反之返回false
 */

bool look_path(char *matrix , int rows, int cols, int row, int col, int path_length, char *str, int *visited)
{
	bool             rv = false;//递归函数返回值

	if(visited == NULL)//非法输入
	{
		return false;
	}
	if(str[path_length] == '\0')
	{
		return true;//说明已经找到了了路径
	}


	if((row >= 0) && (row < rows) && (col >= 0) && (col < cols) && (matrix[row*cols + col] == str[path_length]) && (!visited[row*cols + col]))
	{
		printf("当前格子:%c\n",matrix[row*cols + col]);
		path_length++;//路径+1
		visited[row*cols + col] = 1;//标记这个元素已经走过了

		//开始左右上下寻找路径;
		rv = look_path(matrix,rows,cols,row,col-1,path_length,str,visited)||
			look_path(matrix,rows,cols,row,col+1,path_length,str,visited)||
			look_path(matrix,rows,cols,row-1,col,path_length,str,visited)||
			look_path(matrix,rows,cols,row+1,col,path_length,str,visited);

		//判断在当层中左上右下是否路径
		if(!rv)
		{
			path_length--;//路径长度-1表示回溯了一个格子
			visited[row*cols+col] = 0;//下一次还可以过来寻找
		}
	}

	return rv;
}


int main(int argc,char **argv)
{
	char board[3][4] = {'A','B','C','E','S','F','C','S','A','D','E','E'};
	char word[6] = {'A','B','C','C','E','E'};
	bool rv = false;
	int  col = 4;

	char *p = (char *)board;

	rv = exist(&p, 3, &col,word);
	
	if(rv == true)
	{
		printf("find it\n");
	}
	else
	{
		printf("have not\n");
	}

	return 0;


}
